package letcode.oneQuestionPerDay._202004._26;

import letcode.util.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Description: 合并k个排序链表
 * @Date: 2020/4/26
 * @Author: 许群星
 */
public class MergeKLinkedList_b {
    public static void main(String[] args) {
        ListNode[] lists = new ListNode[3];
        ListNode first = new ListNode(1);
        first.next = new ListNode(3);
        first.next.next = new ListNode(4);

        ListNode second = new ListNode(1);
        second.next = new ListNode(4);
        second.next.next = new ListNode(5);

        ListNode third = new ListNode(2);
        third.next = new ListNode(6);

        lists[0] = second;
        lists[1] = first;
        lists[2] = third;

        ListNode head = mergeKLists(lists);
        System.out.println(head.val);
        System.out.println(head.next.val);
        System.out.println(head.next.next.val);
        System.out.println(head.next.next.next.val);
        System.out.println(head.next.next.next.next.val);
        System.out.println(head.next.next.next.next.next.val);
        System.out.println(head.next.next.next.next.next.next.val);
        System.out.println(head.next.next.next.next.next.next.next.val);
    }

    //提供方法         分治的方法
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return helper(lists,0,lists.length-1);
    }

    //通过mid将数组一分为二，并不断缩小规模，当规模位1时候返回并开始合并
    //通过合并两个链表，不断增大其规模
    private static ListNode helper(ListNode[] lists, int begin, int end) {
        if (begin == end) {
            return lists[begin];
        }
        int mid=begin+(end-begin)/2;
        ListNode left=helper(lists,begin,mid);
        ListNode right=helper(lists,mid+1,end);
        return mergeTwo(left,right);
    }

    /*排序两个链表  */
    private static ListNode mergeTwo(ListNode a,ListNode b){
        if (a == null || b == null) {
            return a==null?b:a;
        }
        if (a.val <= b.val) {
            a.next = mergeTwo(a.next, b);
            return a;
        } else {
            b.next=mergeTwo(a,b.next);
            return b;
        }
    }
}
/*
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */